package com.shm.leetcode;

/**
 * 389. 找不同
 * 给定两个字符串 s 和 t，它们只包含小写字母。
 *
 * 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
 *
 * 请找出在 t 中被添加的字母。
 *
 *
 *
 * 示例 1：
 *
 * 输入：s = "abcd", t = "abcde"
 * 输出："e"
 * 解释：'e' 是那个被添加的字母。
 * 示例 2：
 *
 * 输入：s = "", t = "y"
 * 输出："y"
 * 示例 3：
 *
 * 输入：s = "a", t = "aa"
 * 输出："a"
 * 示例 4：
 *
 * 输入：s = "ae", t = "aea"
 * 输出："a"
 *
 *
 * 提示：
 *
 * 0 <= s.length <= 1000
 * t.length == s.length + 1
 * s 和 t 只包含小写字母
 *
 * @author SHM
 */
public class FindTheDifference {
    /**
     * 方法一：计数
     * @param s
     * @param t
     * @return
     */
    public char findTheDifference(String s, String t) {
        int[] chars=new int[26];
        for(char c:s.toCharArray()){
            chars[c-'a']++;
        }
        for(char c:t.toCharArray()){
            chars[c-'a']--;
        }

        for (int i = 0; i < chars.length; i++) {
            if (chars[i]<0){
                return (char)(i+'a');
            }
        }
        return ' ';
    }

    /**
     * 方法二：求和
     * 将字符串 ss 中每个字符的 ASCII 码的值求和，得到 A_sA
     * s
     * ​
     *  ；对字符串 tt 同样的方法得到 A_tA
     * t
     * ​
     *  。两者的差值 A_t-A_sA
     * t
     * ​
     *  −A
     * s
     * ​
     *   即代表了被添加的字符。
     *   复杂度分析
     *
     * 时间复杂度：O(N)O(N)。
     *
     * 空间复杂度：O(1)O(1)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/find-the-difference/solution/zhao-bu-tong-by-leetcode-solution-mtqf/
     *
     * @param s
     * @param t
     * @return
     */
    public char findTheDifference_2(String s,String t){
        int ss=0,ts=0;
        for(char c:s.toCharArray()){
            ss+=(c-'a');
        }
        for(char c:t.toCharArray()){
            ts+=(c-'a');
        }

        return (char)(ts-ss+'a');
    }
}
